package Demo45;


import java.util.Random;

/**
 * 排序数组
 * https://leetcode.cn/problems/sort-an-array/
 *
 */
class Solution {

    public int[] sortArray(int[] nums) {
        func(nums,0,nums.length -1);
        return nums;
    }

    private void func(int[] nums, int begin, int end) {
        if(begin >= end) {
            return ;
        }
        int key = nums[new Random().nextInt(end - begin + 1) + begin];
        int left = begin - 1,right = end + 1;

        for(int i = begin; i < right;i++) {
            if(nums[i] < key) {
                left++;
                swap(nums,i,left);
            }else if(nums[i] > key) {
                right--;
                swap(nums,right,i);
                i--;
            }
        }
        func(nums,begin,left);
        func(nums,right,end);
    }
    public void swap(int[] nums, int a,int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }

    public int[] sortArray2(int[] nums) {
        qsccort(nums,0,nums.length - 1);
        return nums;
    }

    private void qsccort(int[] nums, int begin, int end) {
        if(begin >= end) {
            return ;
        }
        int left = begin - 1,right = end + 1;
        int key = nums[new Random().nextInt(end - begin + 1) + begin];
        for(int i = begin; i < right;i++) {
            if(nums[i] < key) {
                left++;
                int tmp = nums[left];
                nums[left] = nums[i];
                nums[i] = tmp;
            }else if(nums[i] > key) {
                right--;
                int tmp = nums[right];
                nums[right] = nums[i];
                nums[i] = tmp;
                i--;
            }
        }
        qsccort(nums,begin,left);
        qsccort(nums,right,end);
    }
}
class Demo {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] ret = solution.sortArray(new int[] {5,1,1,2,0,0});
        for(int n : ret) {
            System.out.print(n + " ");
        }
    }
}